{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximize the Beauty of the Garden"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumBeauty"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大化花园的美观度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个花园，有 <code>n</code> 朵花，这些花都有一个用整数表示的美观度。这些花被种在一条线上。给定一个长度为 <code>n</code> 的整数类型数组 <code>flowers</code> ，每一个 <code>flowers[i]</code> 表示第 <code>i</code> 朵花的美观度。</p>\n",
    "\n",
    "<p>一个花园满足下列条件时，该花园是<strong>有效</strong>的。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>花园中至少包含两朵花。</li>\n",
    "\t<li>第一朵花和最后一朵花的美观度相同。</li>\n",
    "</ul>\n",
    "\n",
    "<p>作为一个被钦定的园丁，你可以从花园中<strong>去除</strong>任意朵花（也可以不去除任意一朵）。你想要通过一种方法移除某些花朵，使得剩下的花园变得<strong>有效</strong>。花园的美观度是其中所有剩余的花朵美观度之和。</p>\n",
    "\n",
    "<p>返回你去除了任意朵花（也可以不去除任意一朵）之后形成的<strong>有效</strong>花园中最大可能的美观度。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><b>示例 1：</b></p>\n",
    "\n",
    "<pre><strong>输入:</strong> flowers = [1,2,3,1,2]\n",
    "<strong>输出:</strong> 8\n",
    "<strong>解释:</strong> 你可以修整为有效花园 [2,3,1,2] 来达到总美观度 2 + 3 + 1 + 2 = 8。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> flowers = [100,1,1,-3,1]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong> 你可以修整为有效花园 [1,1,1] 来达到总美观度 1 + 1 + 1 = 3。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> flowers = [-1,-2,0,-1]\n",
    "<strong>输出:</strong> -2\n",
    "<strong>解释:</strong> 你可以修整为有效花园 [-1,-1] 来达到总美观度 -1 + -1 = -2。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= flowers.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= flowers[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li>去除一些花朵（可能没有）后，是有可能形成一个有效花园的。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximize-the-beauty-of-the-garden](https://leetcode.cn/problems/maximize-the-beauty-of-the-garden/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximize-the-beauty-of-the-garden](https://leetcode.cn/problems/maximize-the-beauty-of-the-garden/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,1,2]', '[100,1,1,-3,1]', '[-1,-2,0,-1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        n = len(flowers)\n",
    "        pre = [0] * (n + 1)\n",
    "        res = float('-inf')\n",
    "        dic = {}\n",
    "        for i, v in enumerate(flowers):\n",
    "            pre[i + 1] = pre[i]\n",
    "            if v in dic:\n",
    "                # 计算两个相同值之间正数之和+值本身*2\n",
    "                res = max(res, pre[i] - pre[dic[v] + 1] + v * 2)\n",
    "            else:\n",
    "                dic[v] = i\n",
    "            # 前缀和仅仅累加正数\n",
    "            if v > 0:\n",
    "                pre[i + 1] += v\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "'''\n",
    "题目名： 1788. Maximize the Beauty of the Garden\n",
    "思路：枚举所有收尾的数值，对于每一个数值，必然是第一次出现的位置和最后一次出现的位置配对，能够让中间填充最多的\n",
    "正数，对所有正数求前缀和可以方便求出区段内的正数和，枚举所有可能的配对位置，同时计算区段内正数的和和两端数值的\n",
    "加和即可\n",
    "\n",
    "'''\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        n = len(flowers)\n",
    "        S = [0] * n\n",
    "        if flowers[0] > 0:\n",
    "            S[0] = flowers[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            S[i] = S[i-1] + flowers[i] if flowers[i] > 0 else S[i-1]\n",
    "\n",
    "        first_pos, last_pos = {}, {}\n",
    "        val_set = set()\n",
    "        for idx, val in enumerate(flowers):\n",
    "            if val not in first_pos:\n",
    "                first_pos[val] = idx\n",
    "            last_pos[val] = idx\n",
    "            val_set.add(val)\n",
    "\n",
    "        ans = -0x7ffffffff\n",
    "        for val in val_set:\n",
    "            pos1, pos2 = first_pos[val], last_pos[val]\n",
    "            if pos2 == pos1:\n",
    "                continue\n",
    "\n",
    "            cur_tot = val * 2\n",
    "            if pos2 - pos1 >= 1:\n",
    "                cur_tot += S[pos2-1] - S[pos1]\n",
    "            ans = max(ans, cur_tot)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        n = len(flowers)\n",
    "        pre = [0] * (n +1) \n",
    "        for i in range(1, n+1):\n",
    "            if flowers[i-1] >= 0:\n",
    "                pre[i] = pre[i-1] + flowers[i-1] \n",
    "            else:\n",
    "                pre[i] = pre[i-1] \n",
    "        mx = defaultdict(lambda : float('-inf'))\n",
    "        mn = defaultdict(lambda : float('inf')) \n",
    "        for i, x in enumerate(flowers):\n",
    "            mx[x] = max(mx[x], i) \n",
    "            mn[x] = min(mn[x], i)\n",
    "\n",
    "        ans = float('-inf')\n",
    "        for x in mx:\n",
    "            if mx[x] > mn[x]:\n",
    "                ans = max(ans, x * 2 + pre[mx[x]] - pre[mn[x]+1])\n",
    "        return ans \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        s = [0] * (len(flowers) + 1)\n",
    "        d = {}\n",
    "        ans = -inf\n",
    "        for i, v in enumerate(flowers):\n",
    "            if v in d:\n",
    "                ans = max(ans, s[i] - s[d[v] + 1] + v * 2)\n",
    "            else:\n",
    "                d[v] = i\n",
    "            s[i + 1] = s[i] + max(v, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        pre=[0]*(len(flowers)+1)\n",
    "        res=-inf\n",
    "        dic={}\n",
    "        for i,v in enumerate(flowers):\n",
    "            pre[i+1]=pre[i]\n",
    "            if v in dic:\n",
    "                # 计算两个相同值之间正数之和+值本身*2\n",
    "                res=max(res,pre[i]-pre[dic[v]+1]+v*2)\n",
    "            else:\n",
    "                dic[v]=i\n",
    "            # 前缀和仅仅累加正数\n",
    "            if v>0:\n",
    "                pre[i+1]+=v\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        n = len(flowers)\n",
    "        pre = [0] * (n + 1)\n",
    "        res = float('-inf')\n",
    "        dic = {}\n",
    "        for i, v in enumerate(flowers):\n",
    "            pre[i + 1] = pre[i]\n",
    "            if v in dic:\n",
    "                # 计算两个相同值之间正数之和+值本身*2\n",
    "                res = max(res, pre[i] - pre[dic[v] + 1] + v * 2)\n",
    "            else:\n",
    "                dic[v] = i\n",
    "            # 前缀和仅仅累加正数\n",
    "            if v > 0:\n",
    "                pre[i + 1] += v\n",
    "        return res\n",
    "               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        n = len(flowers)\n",
    "        pre = [0] * (n + 1)\n",
    "        res = float('-inf')\n",
    "        dic = {}\n",
    "        for i, v in enumerate(flowers):\n",
    "            pre[i + 1] = pre[i]\n",
    "            if v in dic:\n",
    "                # 计算两个相同值之间正数之和+值本身*2\n",
    "                res = max(res, pre[i] - pre[dic[v] + 1] + v * 2)\n",
    "            else:\n",
    "                dic[v] = i\n",
    "            # 前缀和仅仅累加正数\n",
    "            if v > 0:\n",
    "                pre[i + 1] += v\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        n=len(flowers)\n",
    "        pre=[0]*(n+1)\n",
    "        dic={}\n",
    "        res=-float(\"inf\")\n",
    "        for i,v in enumerate(flowers):\n",
    "            pre[i+1]=pre[i]\n",
    "            if v not in dic:\n",
    "                dic[v]=i\n",
    "            elif v in dic:\n",
    "                res=max(res,pre[i]-pre[dic[v]+1]+2*v)\n",
    "            if v>=0:\n",
    "                pre[i+1]+=v\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        n = len(flowers)\n",
    "        presum = [0]\n",
    "        for f in flowers:\n",
    "            presum.append(presum[-1] + max(0, f))\n",
    "        left = {}\n",
    "        right = {}\n",
    "        for i in range(n):\n",
    "            if flowers[i] not in left:\n",
    "                left[flowers[i]] = i\n",
    "            right[flowers[i]] = i \n",
    "        res = - float('inf')\n",
    "        for f in left:\n",
    "            if left[f] != right[f]:\n",
    "                res = max(res, presum[right[f]] - presum[left[f] + 1] + f * 2)\n",
    "        return res \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        n = len(flowers)\n",
    "        prefix = [0] * (n + 1)\n",
    "        beauty = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            if len(beauty[flowers[i]]) < 2: beauty[flowers[i]].append(i)\n",
    "            else:   beauty[flowers[i]][1] = i\n",
    "            prefix[i + 1] = prefix[i] + max(0, flowers[i])\n",
    "        \n",
    "        maxVal = -float(inf)\n",
    "        for key in beauty:\n",
    "            if len(beauty[key]) == 2:\n",
    "                maxVal = max(maxVal, 2 * key + prefix[beauty[key][1]] - prefix[beauty[key][0] + 1])\n",
    "        return maxVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        import functools\n",
    "        n=len(flowers)\n",
    "        p=[0]\n",
    "        for num in flowers:p.append(p[-1]+max(0,num)) # 前缀和计算大于0的数\n",
    "        dic={} # 字典记录数字的位置\n",
    "        res=float('-inf')\n",
    "        for j,num in enumerate(flowers):\n",
    "            if num in dic:\n",
    "                i=dic[num]\n",
    "                res=max(res,2*num+p[j]-p[i+1])\n",
    "            else:\n",
    "                dic[num]=j \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        n=len(flowers)\n",
    "        pre=[0]*(n)\n",
    "        dic=collections.defaultdict(list)\n",
    "        res=-float(\"inf\")\n",
    "        for i,v in enumerate(flowers):\n",
    "            if v in dic:\n",
    "                if len(dic[v])==2:\n",
    "                    dic[v][1]=i\n",
    "                elif len(dic[v])==1:\n",
    "                    dic[v].append(i)\n",
    "            else:\n",
    "                dic[v].append(i)\n",
    "        for i,v in enumerate(flowers):\n",
    "            if v<=0:\n",
    "                flowers[i]=0\n",
    "        pre[0]=flowers[0]\n",
    "        for i in range(1,n):\n",
    "            pre[i]=pre[i-1]+flowers[i]\n",
    "        pre=[0]+pre\n",
    "        for x in dic:\n",
    "            if len(dic[x])==2:\n",
    "                s=dic[x][0]\n",
    "                e=dic[x][1]+1\n",
    "                if x>=0:\n",
    "                    res=max(res,pre[e]-pre[s])\n",
    "                elif x<0:\n",
    "                    res=max(res,pre[e]-pre[s]+2*x)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        import functools\n",
    "        n=len(flowers)\n",
    "        p=[0]\n",
    "        for num in flowers:p.append(p[-1]+max(0,num))\n",
    "        dic={}    \n",
    "        res=float('-inf')\n",
    "        for j,num in enumerate(flowers):\n",
    "            if num in dic:\n",
    "                i=dic[num]\n",
    "                res=max(res,2*num+p[j]-p[i+1])\n",
    "            else:\n",
    "                dic[num]=j \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "\n",
    "        d=[]\n",
    "        sum_num=0\n",
    "        for i in flowers:\n",
    "            if i>=0:\n",
    "                sum_num+=i\n",
    "            d.append(sum_num)\n",
    "\n",
    "        dic={}\n",
    "        result=float(\"-inf\")\n",
    "        for idt in range(len(flowers)):\n",
    "\n",
    "            if dic.get(flowers[idt])==None:\n",
    "                dic[flowers[idt]]=idt\n",
    "            else: \n",
    "                num=d[idt-1]-d[dic[flowers[idt]]]+flowers[idt]*2\n",
    "                result=max(num,result)\n",
    "\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "\n",
    "        d=[]\n",
    "        sum_num=0\n",
    "        for i in flowers:\n",
    "            if i>=0:\n",
    "                sum_num+=i\n",
    "            d.append(sum_num)\n",
    "        print(d)\n",
    "        dic={}\n",
    "        result=float(\"-inf\")\n",
    "        for idt in range(len(flowers)):\n",
    "\n",
    "            if dic.get(flowers[idt])==None:\n",
    "                dic[flowers[idt]]=idt\n",
    "            else: \n",
    "                num=d[idt-1]-d[dic[flowers[idt]]]+flowers[idt]*2\n",
    "                result=max(num,result)\n",
    "\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        import functools\n",
    "        n=len(flowers)\n",
    "        p=[0]\n",
    "        for num in flowers:p.append(p[-1]+max(0,num))\n",
    "        dic={}    \n",
    "        res=float('-inf')\n",
    "        for j,num in enumerate(flowers):\n",
    "            if num in dic:\n",
    "                i=dic[num]\n",
    "                res=max(res,2*num+p[j]-p[i+1])\n",
    "            else:\n",
    "                dic[num]=j \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        # import functools\n",
    "        # n=len(flowers)\n",
    "        # p=[0]\n",
    "        # for num in flowers:p.append(p[-1]+max(0,num))\n",
    "        # dic={}    \n",
    "        # res=float('-inf')\n",
    "        # for j,num in enumerate(flowers):\n",
    "        #     if num in dic:\n",
    "        #         i=dic[num]\n",
    "        #         res=max(res,2*num+p[j]-p[i+1])\n",
    "        #     else:\n",
    "        #         dic[num]=j \n",
    "        # return res\n",
    "\n",
    "        sm = [0]\n",
    "        for num in flowers:\n",
    "            sm.append(sm[-1]+max(0,num))\n",
    "        # print(sm)\n",
    "        dic = {}\n",
    "        res = -float('inf')\n",
    "        for i,num in enumerate(flowers):\n",
    "            # print(dic)\n",
    "            if num not in dic:\n",
    "                dic[num] = i\n",
    "            else:\n",
    "                index = dic[num]\n",
    "                res = max(res,sm[i]-sm[index+1]+2*num)\n",
    "            # print(res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        ref = defaultdict(lambda : [inf, -inf])\n",
    "        test = [0]\n",
    "        for i, f in enumerate(flowers):\n",
    "            ref[f][0] = min(ref[f][0], i)\n",
    "            ref[f][1] = max(ref[f][1], i)\n",
    "            if f > 0:\n",
    "                test.append(test[-1] + f)\n",
    "            else:\n",
    "                test.append(test[-1])\n",
    "        ans = -inf\n",
    "        for f in ref:\n",
    "            if ref[f][0] < ref[f][1]:\n",
    "                if f < 0:\n",
    "                    ans = max(ans, test[ref[f][1] + 1] - test[ref[f][0]] + 2 * f)\n",
    "                else:\n",
    "                    ans = max(ans, test[ref[f][1] + 1] - test[ref[f][0]])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        n=len(flowers)\n",
    "        c=collections.defaultdict(list)\n",
    "        pre=[0]*(n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1]=pre[i]\n",
    "            if flowers[i]>0:\n",
    "                pre[i+1]+=flowers[i]\n",
    "            c[flowers[i]].append(i)\n",
    "        ans=-float(\"inf\")\n",
    "        #print(pre)\n",
    "        for key in c:\n",
    "            ls=c[key]\n",
    "            if len(ls)<2:\n",
    "                continue\n",
    "            s,e=ls[0],ls[-1]\n",
    "            #print(s,e)\n",
    "            now=key*2+pre[e]-pre[s+1]\n",
    "            ans=max(ans,now)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        n = len(flowers)\n",
    "        pre = [0]\n",
    "        dic = defaultdict(list)\n",
    "        for i, x in enumerate(flowers):\n",
    "            dic[x].append(i)\n",
    "            pre.append(pre[-1] + max(0, x))\n",
    "        ans = -inf\n",
    "\n",
    "        for k, v in dic.items():\n",
    "            if len(v) >= 2:\n",
    "                ans = max(ans, pre[v[-1]] - pre[v[0]+1] + k * 2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict \n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "\n",
    "        n = len(flowers) \n",
    "        f = [0] * (n+1) \n",
    "        for i in range(1, n+1):\n",
    "            f[i] = f[i-1] + (flowers[i-1] if flowers[i-1] > 0 else 0) \n",
    "        \n",
    "        table = defaultdict(list) \n",
    "\n",
    "        for i, x in enumerate(flowers):\n",
    "            table[x].append(i) \n",
    "\n",
    "        ans = float('-inf')\n",
    "        for k in table:\n",
    "            vec = table[k]\n",
    "            if len(vec) < 2:\n",
    "                continue \n",
    "            ans = max(ans, f[vec[-1]+1] - f[vec[0]] + min(2 * k, 0)) \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param flowers:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        idx_map = defaultdict(list)\n",
    "        dp = {}\n",
    "        cache = 0\n",
    "        dp[-1] = 0\n",
    "        for k,v in enumerate(flowers):\n",
    "            if v > 0:\n",
    "                cache += v\n",
    "            dp[k] = cache\n",
    "            idx_map[v].append(k)\n",
    "        ret = -math.inf\n",
    "        for i in idx_map:\n",
    "            ll1 = idx_map[i]\n",
    "            if len(ll1) == 1:\n",
    "                continue\n",
    "            first = ll1[0]\n",
    "            last = ll1[-1]\n",
    "            ret = max(ret, dp[last-1] - dp[first] + 2 * i)\n",
    "        return ret\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
